---
title: "换零钞"
created: 2025-11-28
tags:
  - 算法
---

# 换零钞

## 题目 [换零钞](https://www.lanqiao.cn/paper/3851/problem/626/)

![[image-e37740d6.png]]

## 思路分析

起初考虑dfs枚举所有可能 但效率太低 半天出不来结果

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int res = 300;  // 用来记录最小的钞票数，初始设为一个比较大的值

void dfs(int sum, int cnt1, int cnt2, int cnt5) {

    if(sum > 200) return;  // 如果累计金额超过200，停止递归

    if(cnt1 > 0 && cnt2 > 0 && cnt5 > 0 && sum == 200) {  // 确保每种面额至少有1张

        if(cnt2 == 10 * cnt1) {  // 检查是否满足2元是1元的10倍

            res = min(res, cnt1 + cnt2 + cnt5);

        }

        return;

    }

    // 继续进行递归搜索，考虑添加1元、2元和5元

    dfs(sum + 1, cnt1 + 1, cnt2, cnt5);

    dfs(sum + 2, cnt1, cnt2 + 1, cnt5);

    dfs(sum + 5, cnt1, cnt2, cnt5 + 1);

}

int main() {

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    dfs(0, 0, 0, 0);

    cout << res << endl;

    return 0;

}
```

改进为直接迭代

1. 直接迭代 1 元和 2 元的数量，计算出必须的 5 元数量来达到 200 元。
2. 根据 2 元的张数是 1 元的 10 倍这一条件进行迭代

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int INF=300;

int main() {

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int res = INF;

    // cnt1代表1元的数量，cnt2代表2元的数量，cnt5代表5元的数量

    // 由于2元的数量是1元的10倍，因此cnt1和cnt2可以直接通过cnt1计算得到

    for (int cnt1 = 1; cnt1 <= 200; ++cnt1) {

        int cnt2 = 10 * cnt1; // 2元的数量是1元的10倍

        if (cnt2 > 200) break; // 如果2元的总额已超过200元，则停止循环

        int remaining = 200 - cnt1 - 2 * cnt2; // 计算剩余金额

        if (remaining < 0) continue; // 如果剩余金额为负，则当前组合无效

        if (remaining % 5 == 0) { // 剩余金额必须能被5整除才合理

            int cnt5 = remaining / 5; // 计算5元的数量

            res = min(res, cnt1 + cnt2 + cnt5); // 更新最小钞票数量

        }

    }

    if (res == INF)

        cout << "Can't found." << endl;

	else

        cout << res << endl;

    return 0;

}
```

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int INF=300;

int main() {

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int res = INF;

    // cnt1代表1元的数量，cnt2代表2元的数量，cnt5代表5元的数量

    // 由于2元的数量是1元的10倍，因此cnt1和cnt2可以直接通过cnt1计算得到

    for (int cnt1 = 1; cnt1 <= 200; ++cnt1) {

        int cnt2 = 10 * cnt1; // 2元的数量是1元的10倍

        if (cnt2 > 200) break; // 如果2元的总额已超过200元，则停止循环

        int remaining = 200 - cnt1 - 2 * cnt2; // 计算剩余金额

        if (remaining < 0) continue; // 如果剩余金额为负，则当前组合无效

        if (remaining % 5 == 0) { // 剩余金额必须能被5整除才合理

            int cnt5 = remaining / 5; // 计算5元的数量

            res = min(res, cnt1 + cnt2 + cnt5); // 更新最小钞票数量

        }

    }

    if (res == INF)

        cout << "Can't found." << endl;

	else

        cout << res << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[第九届蓝桥杯大赛软件赛决赛C-C++ 大学 B 组|第九届蓝桥杯大赛软件赛决赛C/C++ 大学 B 组]] 🏠 [[00-冲刺国赛]] ➡️ [[激光样式|激光样式]]